package com.jack.leetcode.eachproblem_2020;

/**
 * Created by zhang_j on 2020/10/26
 */
public class 有多少小于当前数字的数字 {

    public static void main(String[] args) {
        int[] a = {5,0,10,0,10,6};
        smallerNumbersThanCurrent(a);
    }

    public static int[] smallerNumbersThanCurrent(int[] nums) {
        if(nums == null || nums.length == 0){
            return null;
        }
        int n = nums.length;
        int[] result = new int[n];
        int[] count = new int[101];
        for(int i = 0;i < n;i++){
            count[nums[i]]++;
        }
        int pre = count[0], cur;
        count[0] = 0;
        for(int i = 1;i < count.length;i++){
            cur = count[i];
            count[i] = pre;
            pre += cur;
        }
        for(int i = 0;i < n;i++){
            result[i] = count[nums[i]];
        }
        return result;
    }

    private void quickSort(int[] nums, int[] indexs, int begin, int end){
        if(begin >= end){
            return;
        }
        int i = begin, j = end, num = nums[begin];
        while(i < j){
            while(i < j && num < nums[j]){
                j--;
            }
            if(i < j){
                indexs[i] = j;
                nums[i++] = nums[j];
            }
            while(i < j && num > nums[i]){
                i++;
            }
            if(i < j){
                indexs[j] = i;
                nums[j--] = nums[i];
            }
        }
        nums[i] = num;
        indexs[i] = begin;
        quickSort(nums, indexs, begin, i - 1);
        quickSort(nums, indexs, i - 1, end);
    }
}
